package com.liang.leetcode.binarytree.exercise;

import com.liang.leetcode.binarytree.entity.TreeNode;
import com.liang.leetcode.binarytree.util.BiTreeUtil;

import java.util.*;

/**
 * 513.找树左下角的值
 */
public class BiTree14_FindBottomLeftValue {
    public static void main(String[] args) {
        // 创建一棵二叉树
        List<Integer> nodeList = Arrays.asList(1, 2, 3, 4, null, 5, 6, null, null, null, null, 7);
        TreeNode root = BiTreeUtil.createBiTreeByRecursion(nodeList);
        System.out.println("先序遍历：" + BiTreeUtil.preorderTraversal(root));
        // 二叉树左下角的值
        System.out.println(findBottomLeftValue2(root));
    }

    /**
     * 思路1：递归，前序遍历（根 左 右）
     */
    private static int maxDepth = -1; // 记录最大深度
    private static int value = 0; // 记录树左下角的值

    private static int findBottomLeftValue(TreeNode root) {
        traversal(root, 0);
        return value;
    }

    /**
     * @param root 根节点
     * @param depth 根节点深度
     */
    private static void traversal(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            if (depth > maxDepth) {
                maxDepth = depth;
                value = root.val;
            }
        }
        traversal(root.left, depth + 1);
        traversal(root.right, depth + 1);
    }

    /**
     * 思路2：迭代，层序遍历，同一层的最左节点、不同层的最深层节点
     */
    private static int findBottomLeftValue2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 保存最左节点的值，有更深一层的节点就不断更新
        int leftValue = 0;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                // 如果是当前层的第一个节点，则更新最左值
                if (i == 0) {
                    leftValue = node.val;
                }
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        return leftValue;
    }
}
